package _back_tracking

import org.junit.Assert
import org.junit.Test

/**
 *
 * 题型： 回溯 - 排序
 *
 * https://leetcode.cn/problems/palindrome-permutation-ii/description/
 *
 * 267. 回文排列 II
 *
 * 给定一个字符串 s ，返回 其重新排列组合后可能构成的所有回文字符串，并去除重复的组合 。
 *
 * 你可以按 任意顺序 返回答案。如果 s 不能形成任何回文排列时，则返回一个空列表。
 *
 * 示例 1：
 *
 * 输入: s = "aabb”
 * 输出: ["abba”, "baab”]
 *
 * 示例 2：
 * 输入: s = "abc”
 * 输出: []
 *
 * 提示：
 *
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 */


class LeetCode_217 {
    @Test
    fun test_1() {
        val result = generatePalindromes("aabb")
        val actual = listOf("abba", "baab");
        Assert.assertEquals(result.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val result = generatePalindromes("abc")
        val actual = listOf<String>();
        Assert.assertEquals(result.toString(), actual.toString())
    }
}

private fun generatePalindromes(s: String): List<String> {
    // TODO: convert string to ChartArray
    val array = s.toCharArray()
    // TODO: sort
    array.sort()
    val result: ArrayList<String> = ArrayList()
    backtracking(array, result, BooleanArray(array.size))
    return result
}

private var path: String = ""
private fun backtracking(s: CharArray, result: ArrayList<String>, usedArray: BooleanArray) {
    // 1 终止条件
    if (s.isEmpty()) {
        return
    }
    // 2 收集节点
    if (s.size == path.length) {
        // 判断是否是回文，也可以放在for循环
        if (path.reversed() == path) {
            result.add(path)
            println("result=${result.toString()}")
        }
        return
    }
    // 3 单层递归
    for (i in 0 until s.size) {
        // 4 处理节点
        val node = s[i]
        // 树层去重
        if (i > 0 && s[i] == s[i - 1] && usedArray[i - 1] == false) {
            continue
        }
        // 树枝去重
        if (usedArray[i] == true) {
            continue
        }
        // 不是回文
//        val tmpPath = path + node
//        if (tmpPath.length == s.size && tmpPath.reversed() != tmpPath) {
//            return
//        }
        path = path + node
//        println("node=$node, path=$path")
        usedArray[i] = true

        // 5 递归
        backtracking(s, result, usedArray)

        // 6 回溯
        path = path.substring(0 until path.length - 1)
        usedArray[i] = false
    }

//private fun backtracking(s: CharArray, path: String, result: ArrayList<String>, usedArray: BooleanArray) {
//    // 1 终止条件
//    if (s.isEmpty()) {
//        return
//    }
//    // 2 收集节点
//    if (s.size == path.length) {
//        // 判断是否是回文，也可以放在for循环
//        if (path.reversed() == path) {
//            result.add(path)
//            println("result=${result.toString()}")
//        }
//        return
//    }
//    // 3 单层递归
//    for (i in 0 until s.size) {
//        // 4 处理节点
//        val node = s[i]
//        // 树层去重
//        if (i > 0 && s[i] == s[i - 1] && usedArray[i - 1] == false) {
//            continue
//        }
//        // 树枝去重
//        if (usedArray[i] == true) {
//            continue
//        }
//        // 不是回文
////        val tmpPath = path + node
////        if (tmpPath.length == s.size && tmpPath.reversed() != tmpPath) {
////            return
////        }
//        usedArray[i] = true
//
//        // 5 递归
//        // path 放在 函数参数中，不需要回溯了
//        backtracking(s, path + node, result, usedArray)
//
//        // 6 回溯
//        usedArray[i] = false
//    }
}

